<head>
    <meta charset="UTF-8">
<title>算法训练 结点选择</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div class="sec_header">
问题描述</div>
<div class="sec_cont">
	<p>有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？</p>
</div>
<div class="sec_header">
输入格式</div>
<div class="sec_cont">
	<p>第一行包含一个整数 n 。</p>
	<p>接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。</p>
	<p>接下来一共 n-1 行，每行描述树上的一条边。</p>
</div>
<div class="sec_header">
输出格式</div>
<div class="sec_cont">
	输出一个整数，代表选出的点的权值和的最大值。
</div>
<div class="sec_header">
样例输入</div>
<div class="sec_text">
5<br />
1 2 3 4 5<br />
1 2<br />
1 3<br />
2 4<br />
2 5
</div>
<div class="sec_header">
样例输出</div>
<div class="sec_text">
12
	</div>
<div class="sec_header">
样例说明</div>
<div class="sec_cont">
选择3、4、5号点，权值和为 3+4+5 = 12 。
</div>
<div class="sec_header">
数据规模与约定</div>
<div class="sec_cont">
<p>对于20%的数据， n &lt;= 20。</p>
<p>对于50%的数据， n &lt;= 1000。</p>
<p>对于100%的数据， n &lt;= 100000。</p>
<p>权值均为不超过1000的正整数。</p>
</div>
